﻿using System.Collections.Generic;

namespace SortAndDatastruct {
    /// <summary>
    /// 桶排序算法[需要额外空间]
    /// 该算法效率O(n).因为假设输入有一定的范围
    /// 将数据通过GetBucket()的函数放入一个桶中（该函数也许会很复杂），
    /// 使得各个桶中的数据均匀才能将算法的效率发挥出来。
    /// 一般来讲会在放入桶中之后，对桶中的小部分数据进行排序，这个排序方法可以让你自己选择。
    /// 如果把桶中的数据看成是链状，则可以使用插入排序。(一般也这么实现)
    /// 本实现，在内部的排序算法的实现过程中偷了懒，使用了框架中存在的数据结构List<int> 来完成
    /// </summary>
    class BucketSort : ISort {
        /// <summary>
        /// 获取桶的编号
        /// </summary>
        /// <param name="Num">需要放入桶中的数据</param>
        /// <returns>桶的编号</returns>
        int GetBucket(int Num) {
            if (Num < 0) return 0;
            if (Num >= 100) return 9;//只设置了10个桶
            return Num / 10;
        }
        /// <summary>
        /// 排序接口
        /// </summary>
        /// <param name="Array">带排序的数组</param>
        internal override void Sort(ref int[] Array) {
            if (Array == null || Array.Length < 2) return;
            List<int>[] buckets = new List<int>[10];
            for (int i = 0; i < 10; ++i) {
                buckets[i] = new List<int>();
            }
            for (int i = 0; i < Array.Length; ++i) {
                int bucketNum = GetBucket(Array[i]);
                buckets[bucketNum].Add(Array[i]);
                buckets[bucketNum].Sort();//也可以在装桶完毕之后进行排序，依据具体实现来
            }
            int j = 0;
            foreach (var item in buckets) {
                if (item != null && item.Count != 0) {
                    item.CopyTo(Array, j);
                    j += item.Count;
                }
            }
        }
    }
}
